%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% input
\KwIn{A connected graph $G$.}
%%
%% output
\KwOut{A spanning tree of $G$.}
\BlankLine
%%
%% algorithm body
$T \assign G$\;
\While{\rm $T$ is not a tree}{
  $e \assign$ random edge of $T$\;
  \If{\rm $T - e$ is connected}{
    $T \assign T - e$\;
  }
}
\Return $T$\;
